void Swap(int*x,int*y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}
////////////////////三数取中法 选择k
int GetMidi(int* a,int left,int right)
{
    int mid = (left + right)/2;

    //保证left MAX
    if(a[left] < a[mid])
        Swap(&left,&mid);

    if(a[left] < a[right])
        Swap(&left,&right);

    //保证mid是第二大的
    if(a[mid] < a[right])
        Swap(&right,&mid);
    return mid;
}
//快速排序（Hoare）
void QuickSort1(int* a,int left,int right)
{
    if(left >= right)
        return;
    int begin = left;
    int end = right;
    int mid = GetMidi(a,begin,end);
    Swap(&a[left],&a[mid]);
    int key = left;

    while(left < right)
    {
        while(left < right && a[right] >= a[key])
        {
            right--;
        }
        while (left < right && a[left] <= a[key])
        {
            left++;
        }
        Swap(&a[left],&a[right]);
    }
    Swap(&a[left],&a[key]);

    QuickSort1(a,begin,left-1);
    QuickSort1(a,left+1,end);
}
///////////////////快速排序（挖坑法）
void QuickSort2(int* a,int left,int right)
{
    if(left >= right)
        return;

    int begin = left;
    int end = right;

    int mid = GetMidi(a,begin,end);
    Swap(&a[left],&a[mid]);
    int key = a[left];
    int hole = left;

    while (left < right)
    {
        while(left < right && a[right] >= key)
        {
            right--;
        }
        a[hole] = a[right];
        hole = right;
        while (left < right && a[left] <= key)
        {
            left++;
        }
        a[hole] = a[left];
        hole = left;
    }
    a[hole] = key;

    QuickSort2(a,begin,hole-1);
    QuickSort2(a,hole+1,end);
}
///////////////////快速排序（前后指针）
void QuickSort3(int* a,int left,int right)
{
    if(left >= right)
        return;

    int begin = left;
    int end = right;

    int mid = GetMidi(a,begin,end);
    Swap(&a[begin],&a[mid]);

    int prev = left;
    int cur = prev + 1;

    int key = left;
    while(cur <= right)
    {
        if(a[cur] < a[key] && ++prev != cur)
        {
            Swap(&a[prev],&a[cur]);
        }
        cur++;
    }
    Swap(&a[key],&a[prev]);
    QuickSort3(a,begin,prev-1);
    QuickSort3(a,prev+1,end);
}